package org.xqh.study.leetcode.algorithm;

import com.sun.media.sound.RIFFReader;

/**
 * @ClassName MaxTurbulenceSize
 * @Description 最长湍流子数组
 * https://leetcode-cn.com/problems/longest-turbulent-subarray/
 * @Author xuqianghui
 * @Date 2021/2/8 10:43
 * @Version 1.0
 */
public class MaxTurbulenceSize {

    public static void main(String[] args) {
        int[] arr = {9, 9, 3, 4, 2, 5, 2, 8, 11, 2};
//        int[] arr = {9, 9, 9, 8};
        System.out.println(maxTurbulenceSize22(arr));
    }



    /**
     * 当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组：
     * <p>
     * 若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
     * 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
     *
     * @param arr
     * @return
     */
    public static int maxTurbulenceSize00(int[] arr) {
        int len = arr.length;
        if (len <= 1) {
            return len;
        }
        if(len == 2){//长度为2 的情况
            return arr[0] == arr[1] ? 1 : 2;
        }
        int[] compare = new int[len - 1];
        for (int i = 0; i < len - 1; i++) {
            int val = 0;
            if (arr[i] > arr[i + 1]) {
                val = 1;
            } else if (arr[i] < arr[i + 1]) {
                val = -1;
            }
            compare[i] = val;
        }

        int maxRet = 0;
        int left = 0;
        for (int i = 0; i < compare.length - 1; i++) {
            if (compare[i] + compare[i + 1] != 0 || compare[i] == 0 || compare[i + 1] == 0) {
                left = i + 1;
                if(compare[i] == 0 && compare[i+1] == 0){
                    left ++;
                }
            }
            maxRet = Math.max(maxRet, i - left + 3);
        }
        return maxRet;
    }

    /**
     * 动态规划
     * @param arr
     * @return
     */
    public static int maxTurbulenceSize11(int[] arr){
        int len = arr.length;
        if(len <= 1){
            return len;
        }
        if(len == 2){
            return arr[0] == arr[1] ? 1 : 2;
        }
        int res = 0;
        int incrLen = 1;
        int descLen = 1;
        for(int i = 1; i < len; i++){
            if(arr[i] < arr[i - 1]){
                incrLen = descLen + 1;
                descLen = 1;
            }else if(arr[i] > arr[i-1]){
                descLen = incrLen + 1;
                incrLen = 1;
            }else {
                //相等的情况
                descLen = 1;
                incrLen = 1;
            }
            res = Math.max(res, Math.max(incrLen, descLen));
        }
        return res;
    }

    /**
     * 双指针
     * @param arr
     * @return
     */
    public static int maxTurbulenceSize22(int[] arr){
        int len = arr.length;
        if(len <= 1){
            return len;
        }
        if(len == 2){
            return arr[0] == arr[1] ? 1 : 2;
        }
        int res = 0;
        /**
         * left 左指针, 标识当前 湍流子数组 左边界
         * right 标识当前湍流子数组 右边界
         */
        boolean pre = false;//记录前一个 对比的 结果
        for(int left = 0, right = 1; right < len; right ++){
            boolean cur = arr[right] > arr[right - 1];
            if(right == 1 ||  cur == pre){
                //相同的话
                left = right - 1;
            }

            if(arr[right] == arr[right - 1]){
                //移动 左指针
                left = right;
            }
            res = Math.max(res, right - left + 1);
            pre = cur;
        }
        return res;
    }
}
